//
// Created by daiyizheng on 2022/3/27.
//
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
//前缀和+DFS

int dfs(TreeNode* node, vector<int> &parentPathSumList, int targetSum){
    if (node== nullptr)return 0;

    vector<int> tmp;
    int cnt=0;
    for (int num:parentPathSumList){
        int s = num+node->val;
        tmp.push_back(s);
        if (s==targetSum)cnt++;
    }
    tmp.push_back(node->val);
    if(node->val==targetSum)cnt++;

    int leftCnt = dfs(node->left, tmp, targetSum);
    int rightCnt = dfs(node->right, tmp, targetSum);

    return cnt+leftCnt+rightCnt;
}
int pathSum(TreeNode* root, int targetSum) {
    vector<int> tmp;
    return dfs(root, tmp, targetSum);
}



//
#include <unordered_map>
// DFS + 前缀和
int dfs1(TreeNode* node, int currSum, int target, unordered_map<int, int>& prefixSumMap) {
    if (node == nullptr) return 0;

    currSum += node->val;
    int res = prefixSumMap[currSum - target];
    prefixSumMap[currSum] = prefixSumMap[currSum] + 1;

    res += dfs1(node->left, currSum, target, prefixSumMap);
    res += dfs1(node->right, currSum, target, prefixSumMap);

    prefixSumMap[currSum] = prefixSumMap[currSum] - 1;
    return res;
}
int pathSum1(TreeNode* root, int sum) {
    unordered_map<int, int> prefixSumMap;
    prefixSumMap[0] = 1;
    return dfs1(root, 0, sum, prefixSumMap);
}



